package algorithms.graph;

import java.util.Stack;

public class DirectedCycle {

	private boolean[] marked;
	private int[] edgeTo;	//记录深度优先的轨迹
	private Stack<Integer> cycle;
	private boolean[] onStack;
	
	public DirectedCycle(Digraph G) {
		onStack = new boolean[G.V()];
		edgeTo  = new int[G.V()];
		marked  = new boolean[G.V()];
		for(int v=0;v<G.V();v++){
			if(!marked[v]) dfs(G,v);
		}
	}

	private void dfs(Digraph g, int v) {
		onStack[v] = true;	//true，便于跟踪
		marked[v] = true;
		for(int w : g.adj(v)){
			if(hasCycle())	return;
			else if(!marked[w]){
				edgeTo[w] = v;
				dfs(g, w);
			}else if(onStack[w]){
				cycle = new Stack<Integer>();
				for(int x = v; x != w; x = edgeTo[x]){
					cycle.push(x);
				}
				cycle.push(w);
				cycle.push(v);
			}
		}
		onStack[v] = false;	//递归结束后修改为false，表示不再栈中
	}
	
	public boolean hasCycle(){
		return this.cycle != null;
	}
	
	public Iterable<Integer> cycle(){
		return cycle;
	}
}
